package Class025;

import Class004.BasicSorts;
import Class021.Merge;
import Utils.ArrayUtils;

import java.util.Arrays;

public class Heap {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        int time = 1000;
        int amount = 10000, max = 100;
        int errTime = 0;
        System.out.println("Correctness Test:");
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            int[] right = Arrays.copyOf(base, base.length);
            int[] better = Arrays.copyOf(base, base.length);
            Merge.myMerge(right, false);
            MyHeap.heapSortFromBottom(better);
            if (!ArrayUtils.judge(right, better)) {
                System.out.println(Arrays.toString(base));
                System.out.println("Should be:");
                System.out.println(Arrays.toString(right));
                System.out.println("Wrong answer:");
                System.out.println(Arrays.toString(better));
                errTime++;
            }
        }
        if (errTime == 0) {
            System.out.println("All clear.");
        } else {
            System.out.println("Errors:" + errTime + "/" + time);
            System.out.println("Accuracy:" + (time - errTime) * 1.0 / time);
            return;
        }

        System.out.println("Time test:");
        long s, e;
        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            MyHeap.heapSortFromTop(base);
        }
        e = System.currentTimeMillis();
        System.out.println("Heap Sort From Top:" + (e - s) + "ms");

        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            MyHeap.heapSortFromBottom(base);
        }
        e = System.currentTimeMillis();
        System.out.println("Heap Sort From Bottom:" + (e - s) + "ms");

        s = System.currentTimeMillis();
        for (int i = 0; i < time; i++) {
            int[] base = ArrayUtils.generateArray(amount, max);
            Merge.myMerge(base, false);
        }
        e = System.currentTimeMillis();
        System.out.println("Merge(Ite):" + (e - s) + "ms");
    }

    //以大根堆为例
    public static class MyHeap {
        public int size;
        public int[] heap;

        public MyHeap(int cap) {
            heap = new int[cap];
        }

        public MyHeap(int[] arr) {
            size = arr.length;
        }

        public void adjust(int[] arr, int pos, int val) {
            if (pos < 0 || pos >= size) {
                System.out.println("Invalid position...");
                return;
            }
            arr[pos] = val;
            heapify(arr, pos, size);
            heapInsert(arr, pos);
        }

        public static void heapInsert(int[] arr, int pos) {
            //如果是大根堆，判断条件改成 > 即可
            //如果是小根堆，判断条件改成 < 即可
            while (arr[pos] > arr[(pos - 1) / 2]) {
                swap(arr, pos, (pos - 1) >> 1);
                pos = (pos - 1) >> 1;
            }
        }

        public static void heapify(int[] arr, int pos, int size) {
            int left = (pos << 1) + 1;
            while (left < size) {
                int right = left + 1;
                //如果是大根堆，判断条件: >
                //如果是小根堆，判断条件: <
                int nextIndex = right < size && arr[right] > arr[left] ?
                        right : left;
                //如果是大根堆，判断条件: <
                //如果是小根堆，判断条件: >
                if (arr[pos] < arr[nextIndex]) {
                    swap(arr, pos, nextIndex);
                    pos = nextIndex;
                    left = (pos << 1) + 1;
                } else break;
            }
        }

        //经典堆排序
        //1. 从顶到底先建立好大根堆，该过程为
        //log2(1) + log2(2) + ... + log2(N) => 收敛于O(N * logN)
        //常量增倍：假设是2N个数加入，常数项不该影响复杂度
        //看看2N时，下限是不是O(N * logN)
        //若上限是它，下限也是它，肯定就是它，夹逼定理...
        //2. 堆排序，O(N * logN)，因为就是上面那个反过来，每次堆少一个
        //整体O(N * logN)
        public static void heapSortFromTop(int[] arr) {
            for(int i = 0; i < arr.length - 1; i++) {
                heapInsert(arr, i);
            }
            int size = arr.length;
            while(size > 1) {
                swap(arr, 0, --size);
                heapify(arr, 0, size);
            }
        }

        //如果从底到顶建堆，是不是更快?
        //思路也很简单。既然从顶部开始建堆，新加进来的是要往上heapInsert
        //那么从底部建，新加进来的只要往下heapify即可
        //为什么变得更快:
        //在第N层，所有这一层的节点是不需要往下动的。而这一层已经占了整棵树一半的节点(假设完全)
        //直观上来说就是快很多，不然按照之前的逻辑，这一层每个节点都要往上Insert
        public static void heapSortFromBottom(int[] arr) {
            //只是这里变了
            for(int i = arr.length - 1; i >= 0; i--) {
                heapify(arr, i, arr.length);
            }
            int size = arr.length;
            while(size > 1) {
                swap(arr, 0, --size);
                heapify(arr, 0, size);
            }
        }

        public void add(int val) {
            if (isFull()) {
                System.out.println("Already Full!");
                return;
            }
            heap[size] = val;
            heapInsert(heap, size++);
        }

        public int getMin() {
            if (isEmpty()) {
                throw new RuntimeException("Cao ni ma, mei le");
            }
            int res = heap[0];
            swap(heap, 0, --size);
            heap[size] = 0;
            heapify(heap, 0, size);
            return res;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == heap.length;
        }

        //如果说用到Map，还要调整map中的记录
        private static void swap(int[] arr, int x, int y) {
            //indexMap(heap[x])....
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
    }
}
